/*!
 * \file vEBTree.h
 * \brief A van Emde Boas tree data structure, implemented with a simple array of words.
 *
 * \date Jun 18, 2012
 * \author correa
 */
#ifndef ARRAYVEBTREE_H_
#define ARRAYVEBTREE_H_

#include<string.h>//necessary to use memset
#include<cstdio>
#include <stdlib.h>
#include "BitTools.h"
#include"vEBTree.h"

template<typename T> class ArrayvEBTreeFactory;

/*!
 * \brief Implementation of vEBTree using a array of words.
 *
 * This class is derived from eVBTree, implemented with a simple array of word as data structure. All the pure virtual
 * methods of vEBTree are implemented and same methods are overwritten in order to make a better use of the array
 * structure.
 *
 * This class is a van Emde Boas tree with implemented as array of words.
 */
template <typename T>
class ArrayvEBTree : public vEBTree<T> {
private:
	T* vector;//!< the array of words
	long vectorsz;//!< the size of vector

public:

	/*!
	 * \brief The index of the specified element in the vector of words.
	 *
	 * This value is given by the floor of the specified element divided by the size of a word.
	 *
	 * \param i the specified element.
	 *
	 * \return The index of the specified element in the vector of words.
	 *
	 */
	virtual long wordIdx(long i);

	/*!
	 *
	 * \brief The index of the specified element in a word.
	 *
	 * This value is given by the remainder of the specified element divided by the size of a word.
	 *
	 * \param i the specified element.
	 *
	 * \return The index of the specified element in a word.
	 *
	 */
	virtual long inWordIdx(long i);

	/*!
	 * \brief The node in the index i of the leaf level of the tree.
	 *
	 * This method should be implemented in each child class. It is to be used used for the
	 * methods in the father class as a way to retrieve nodes in each level of the tree, that
	 * is a vEBTree of only one level.
	 *
	 * \param i the index of the node to be retrieve.
	 */
	virtual T treeNode(long i);

	virtual void setNode(long i, T newnode);

	virtual void setNodeInLevel(long i, T newnode);

	virtual long nextSetInWord(long i);

	virtual long firstSetInWord(long i);

	virtual long nextComplInWord(long i);

	virtual long countSetInWord(long i);

	virtual long countComplInWord(long i);

	virtual void toSetInLevel(long i);

	virtual void toComplInLevel(long i);

	virtual void allToSetInLevel();

	virtual void allToComplInLevel();

public:

	/*!
	 * \brief The base constructor of the class.
	 *
	 * The universe is always a set of natural numbers, starting from 0 until sz-1. Even
	 * if you use a Filter to select some elements in the universe.
	 *
	 * \sa vEBTree(int size)
	 *
	 * \param sz the number of elements in the universe.
	 */
	ArrayvEBTree(int sz);

	ArrayvEBTree(vEBTreeFactory<T>* f, int size, int ht);


	/*!
	 * \brief A destructor.
	 *
	 * All data used are deleted and memory space are cleaned.
	 */
	virtual ~ArrayvEBTree();

	/*!
	 * \brief Create a copy of this object.
	 *
	 * A concrete implementation of this class must override this method in order to perform the copy of the
	 * data structure.
	 *
	 * \return a copy of this object.
	 */
	virtual vEBTree<T>* clone();

	/*!
	 * \brief Determine the next element in the set, in increasing order, of the specified element.
	 *
	 * The smallest element of the universe which is in the set and is greater than the specified element (which is not
	 * required to be in the set). This method is provided by convenience, but it is less efficient than using an iterator provided by
	 * vEBTree<T>::newSetIterator() or vEBTree::newCompllIterator().
	 *
	 * If vEBTree<T>::setIt is not initialized by the derived class, then an error occurs.
	 *
	 * \param i the element from which this method determines the next element.
	 *
	 * \return the first element after the specified one in the set, if exists one; otherwise, a value greater or equal to the size of the universe is returned.
	 */
	long nextSetElementInLevel(long i);

	/*!
	 * \brief Determine the next element in the set, in increasing order, of the specified element.
	 *
	 * The smallest element of the universe which is in the set and is greater than the specified element (which is not
	 * required to be in the set). This method is provided by convenience, but it is less efficient than using an iterator provided by
	 * vEBTree<T>::newSetIterator() or vEBTree::newCompllIterator().
	 *
	 * If vEBTree<T>::setIt is not initialized by the derived class, then an error occurs.
	 *
	 * \param i the element from which this method determines the next element.
	 *
	 * \return the first element after the specified one in the set, if exists one; otherwise, a value greater or equal to the size of the universe is returned.
	 */
	long nextComplElementInLevel(long i);

	/*!
	 * \brief Add the specified element to the set, removing it from the complement.
	 *
	 * As a result of this operation, the specified element appears in an enumeration of the set. It employs the
	 * vEBTree<T>::treeNode to get access to the data structure. A derived class is free to override this method
	 * to obtain more efficient access to the data structure.
	 *
	 * This method is optional. If i is not in the universe a error will occur.
	 *
	 * \param i the element to add.
	 */
	virtual void toSet(long i);

	/*!
	 * \brief Add the specified element to the complement, removing it from the set.
	 *
	 * As a result of this operation, the specified element disappears in an enumeration of the set. It employs the
	 * vEBTree<T>::treeNode to get access to the data structure. A derived class is free to override this method
	 * to obtain more efficient access to the data structure.
	 *
	 * This method is optional. If i is not in the universe a error will occur.
	 *
	 * \param i the element to add.
	 */
	virtual void toCompl(long i);


	/*!
	 * \brief Determines whether the specified element is in this set.
	 *
	 * This is the standard implementation, which traverses the levels of the tree to check the element.
	 * A derived class should override this method to obtain a linear time implementation.
	 *
	 * If the specified element is not valid, it will return false.
	 *
	 * \param i the specified element.
	 *
	 * \return \c true if \c i is in the set, and \c false otherwise.
	 */
	virtual bool isInSet(long i);

	/*!
	 * \brief Determines whether the specified element is in this complement.
	 *
	 * This is the standard implementation, which traverses the levels of the tree to check the element.
	 * A derived class should override this method to obtain a linear time implementation.
	 *
	 * If the specified element is not valid, it will return false.
	 *
	 * \param i the specified element.
	 *
	 * \return \c true if \c i is in the complement, and \c false otherwise.
	 */
	virtual bool isInCompl(long i);


	/*!
	 * \brief Returns an array containing all of the elements in this set in increasing order.
	 *
	 * At the discretion of the implementation, this object may maintain a reference to the returned array.
	 *
	 * This method acts as bridge between array-based and eVBTree-based APIs.
	 *
	 * The size of the vector is returned in the pointer size.
	 *
	 * \param size a pointer to store the number of elements in the set.
	 *
	 * \return an array containing all the elements in this vEBTree.
	 *
	 */
	virtual T * toArray(long* size);

	/*!
	 *  \brief The number of elements present in the universe.
	 *
	 *  This is the value passed as parameter to the constructor, it is important to notice that
	 *  this is not the real size of the tree, actually the real size of the tree is about \f$ 2size\f$.
	 *
	 *
	 *  \return the number of bits used to index all the elements of the universe.
	 */
	virtual long size();

	virtual long sizeInWord();

	/*!
	 *  \brief Add all the elements of the universe to the set.
	 *
	 * The abstract class implement it with by simply call this same method in each level of the
	 * current tree. Each child should implement this method in a very fast way in order to make
	 * the function efficient.
	 */
	virtual void allToSet();

	/*!
	 *  \brief Add all the elements of the universe to the complement.
	 *
	 * The abstract class implement it with by simply call this same method in each level of the
	 * current tree. Each child should implement this method in a very fast way in order to make
	 * the function efficient.
	 */
	virtual void allToCompl();


};

template<typename T>
ArrayvEBTree<T>::~ArrayvEBTree(){
	for(long i = 1; i < vEBTree<T>::height ; i++){
		delete vEBTree<T>::levels[i];
	}
	delete vector;
	delete vEBTree<T>::bitvector;
}

template<typename T>
inline T ArrayvEBTree<T>::treeNode(long i){
	//just retrieve a position in the vector
	return vector[i];
}


template<typename T>
inline ArrayvEBTree<T>::ArrayvEBTree(int sz):vEBTree<T>(sz){
	vectorsz = ((sz >> vEBTree<T>::logb) << vEBTree<T>::logb) == sz? (sz >> vEBTree<T>::logb) : (sz >> vEBTree<T>::logb) + 1;
	if(vectorsz == 0) vectorsz = 1;
	vector = new T[vectorsz];
	vEBTree<T>::levels = new vEBTree<T>*[1];
	vEBTree<T>::levels[0] = this;
	vEBTree<T>::height = 1;
	memset(vector,0, vectorsz*sizeof(T));
}

template<typename T>
ArrayvEBTree<T>::ArrayvEBTree(vEBTreeFactory<T>* f, int size, int ht):vEBTree<T>(size){
	//initialize and allocate memory
	vectorsz = ((size >> vEBTree<T>::logb) << vEBTree<T>::logb) == size? (size >> vEBTree<T>::logb) : (size >> vEBTree<T>::logb) + 1;
	if(vectorsz == 0) vectorsz = 1;
	vector = new T[vectorsz];
	vEBTree<T>::levels = new vEBTree<T>*[ht + 1];
	vEBTree<T>::levels[0] = this;
	memset(vector,0, vectorsz*sizeof(T));
	vEBTree<T>::height = ht + 1;
	int sz = vectorsz;
	for(int i = 1; i <= ht; i++){
		vEBTree<T>::levels[i] = f->getvEBTree(sz);
		sz = ((sz >> vEBTree<T>::logb) << vEBTree<T>::logb) == sz? (sz >> vEBTree<T>::logb) : (sz >> vEBTree<T>::logb) + 1;
		if(sz == 0) sz = 1;
	}

	//link the upper levels of the current tree
	for(int i = 1; i <=ht; i++){
		vEBTree<T>::levels[i]->levels = new vEBTree<T>*[ht + 1 - i];
		vEBTree<T>::levels[i]->height = ht + 1 - i ;
		vEBTree<T>::levels[i]->levels[0] = vEBTree<T>::levels[i];
		for(int j = i+1; j <= ht; j++){
			vEBTree<T>::levels[i]->levels[j - i] = vEBTree<T>::levels[j];
		}
	}
}


template<typename T>
inline vEBTree<T> * ArrayvEBTree<T>::clone(){
	//create the copy
	ArrayvEBTree<T>* clone = new ArrayvEBTree(vEBTree<T>::n);
	//copy the whole vector
	for(long i = 0; i < vectorsz; i++){
		clone->vector[i] = vector[i];
	}
	clone->levels[0] = clone;
	for(long j = 1; j < vEBTree<T>::height; j++){
		clone->levels[j] = vEBTree<T>::levels[j]->clone();
	}
	return clone;
}

template<>
inline long ArrayvEBTree<int>::nextSetElementInLevel(long i){

	if(i <= vEBTree<int>::n){

		long index = wordIdx(i);//index of the word

		//look in the word of i for the next one
		long inword = builtinLeast<int>(vector[index] & posmasksimp[inWordIdx(i)]);

		//if a found it, return
		if(inword != -1) return inword + (index << vEBTree<int>::logb);

		//look in the rest of the vector
		for(long j = index + 1; j < vectorsz; j++){
			inword = builtinLeast<int>(vector[j]);
			if(inword > 0) return inword + (j << vEBTree<int>::logb) ;
		}
	}
	return -1;
}

template<>
inline long ArrayvEBTree<long>::nextSetElementInLevel(long i){

	if(i <= vEBTree<long>::n){

		long index = wordIdx(i);//index of the word

		//look in the word of i for the next one
		long inword = builtinLeast<long>(vector[index] & posmasklsimp[inWordIdx(i)]);

		//if a found it, return
		if(inword != -1) return inword  + (index << vEBTree<long>::logb);

		//look in the rest of the vector
		index++;
		for(long j = index; j < vectorsz; j++){
			inword = builtinLeast<long>(vector[j]);
			if(inword > 0) return inword + (j << vEBTree<long>::logb) ;
		}
	}
	return -1;
}

template<typename T>
inline long ArrayvEBTree<T>::nextComplElementInLevel(long i){
	//for each element, tests if it is in the complement
	for(long j = i; j < vEBTree<T>::n; j++){
		if(isInCompl(j)) return j;
	}
	return -1;
}

template<typename T>
inline long ArrayvEBTree<T>::inWordIdx(long i){
	return i & vEBTree<T>::maskb;
}

template<typename T>
inline long ArrayvEBTree<T>::wordIdx(long i){
	return i >> vEBTree<T>::logb;
}

template<typename T>
inline void ArrayvEBTree<T>::toSetInLevel(long i){
	vector[wordIdx(i)] |= (1LL << (inWordIdx(i)));
}

template<typename T>
inline void ArrayvEBTree<T>::toComplInLevel(long i){
	vector[wordIdx(i)] &= ~(1LL << (inWordIdx(i)));
}

template<typename T>
inline void ArrayvEBTree<T>::toSet(long i){
	vector[wordIdx(i)] |= (1LL << (inWordIdx(i)));
	int j = 1,index = wordIdx(i);

	//update the summary vector if necessary
	while(j < vEBTree<T>::height && vEBTree<T>::levels[j]->isInCompl(index)){
		vEBTree<T>::levels[j]->toSetInLevel(index);
		index = vEBTree<T>::levels[j++]->wordIdx(index);
	}
}

template<typename T>
inline void ArrayvEBTree<T>::toCompl(long i){
	vector[wordIdx(i)] &= ~(1LL << (inWordIdx(i)));
	int j = 1,index = wordIdx(i);

	//update the summary vector if necessary
	while(vEBTree<T>::levels[j-1]->treeNode(index) == 0 && j < vEBTree<T>::height){
		vEBTree<T>::levels[j]->toComplInLevel(index);
		index = vEBTree<T>::levels[j++]->wordIdx(index);
	}
}


template<typename T>
inline bool ArrayvEBTree<T>::isInSet(long i){
	return (vector[wordIdx(i)] & (1LL << (inWordIdx(i)))) != 0;
}

template<typename T>
inline bool ArrayvEBTree<T>::isInCompl(long i){
	return (vector[wordIdx(i)] & (1LL << (inWordIdx(i)))) == 0;
}


template<>
inline long ArrayvEBTree<int>::nextSetInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<int>(vector[wordIdx(i)] & posmasksimp[inWordIdx(i)]);;
}

template<>
inline long ArrayvEBTree<int>::firstSetInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<int>(vector[i]);
}

template<>
inline long ArrayvEBTree<long>::firstSetInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<long>(vector[i]);
}

template<>
inline long ArrayvEBTree<long>::nextSetInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<long>(vector[wordIdx(i)] & posmasksimp[inWordIdx(i)]);
}

template<>
inline long ArrayvEBTree<int>::nextComplInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<int>((~vector[wordIdx(i)]) & posmasksimp[inWordIdx(i)]);
}

template<>
inline long ArrayvEBTree<long>::nextComplInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<long>((~vector[wordIdx(i)]) & posmasksimp[inWordIdx(i)]);
}


template<>
inline long ArrayvEBTree<int>::countSetInWord(long i){
	//using builtin to count
	return builtinCounter<int>(vector[i]);
}

template<>
inline long ArrayvEBTree<long>::countSetInWord(long i){
	//using builtin to count
	return builtinCounter<long>(vector[i]);
}

template<>
inline long ArrayvEBTree<int>::countComplInWord(long i){
	//using builtin to count
	return builtinCounter<int>(~vector[i]);
}

template<>
inline long ArrayvEBTree<long>::countComplInWord(long i){
	//using builtin to count
	return builtinCounter<long>(~vector[i]);
}

template<typename T>
inline void ArrayvEBTree<T>::setNode(long i, T newnode){
	vector[i] = newnode;
	//if has a upper vector, update it
	if(vEBTree<T>::height > 1){
		if(newnode == 0)vEBTree<T>::levels[1]->toCompl(i);
		else vEBTree<T>::levels[1]->toSet(i);
	}
}

template<typename T>
inline void ArrayvEBTree<T>::setNodeInLevel(long i, T newnode){
	vector[i] = newnode;
}

template<typename T>
inline T* ArrayvEBTree<T>::toArray(long* size){
	vEBTree<T>::bitvector = new T[vectorsz];
	for(*size = 0; *size < vectorsz; (*size)++){
		vEBTree<T>::bitvector[*size] = vector[*size];
	}
	return vEBTree<T>::bitvector;
}

template<typename T>
inline long ArrayvEBTree<T>::size(){
	return vEBTree<T>::n;
}

template<typename T>
inline long ArrayvEBTree<T>::sizeInWord(){
	return vectorsz;
}

template<typename T>
inline void ArrayvEBTree<T>::allToSetInLevel(){
	memset(vector, 255, vectorsz*sizeof(T));
}

template<typename T>
inline void ArrayvEBTree<T>::allToSet(){
	memset(vector, 255, vectorsz*sizeof(T));
	for(long i = 1; i < vEBTree<T>::height; i++){
		vEBTree<T>::levels[i]->allToSetInLevel();
	}
}

template<typename T>
inline void ArrayvEBTree<T>::allToComplInLevel(){
	memset(vector, 0, vectorsz*sizeof(T));
}

template<typename T>
inline void ArrayvEBTree<T>::allToCompl(){
	memset(vector, 0, vectorsz*sizeof(T));
	for(long i = 1; i < vEBTree<T>::height; i++){
		vEBTree<T>::levels[i]->allToComplInLevel();
	}
}

template <typename T>
class ArrayvEBTreeFactory : public vEBTreeFactory<T>{
public:

	vEBTree<T>* getvEBTree(long size){
		return new ArrayvEBTree<T>(size);
	}
};

#endif /* ARRAYVEBTREE_H_ */
